/*
它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表
 */

function insertionSort(arr) {
    const len = arr.length;
    for (let i = 1; i < len; i++) {
        const temp = arr[i];
        let j = i - 1;
        while (j >= 0 && arr[j] > temp) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp;
    }
    return arr;
}
// 时间复杂度O(n^2)
const arr = [2,5,4,8,2,1];
console.log(insertionSort(arr));
